package cc.wsyw126.java.nowcoder.interview;

import cc.wsyw126.java.lintCode.swap_two_nodes_in_linked_list.ListNode;

/**
 * Created by Administrator on 2017/4/24.
 * 编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前给定一个链表的头指针 ListNode* pHead，请返回重新排列后的链表的头指针。注意：分割以后保持原来的数据顺序不变。
 */
public class Partition {
    public ListNode partition(ListNode pHead, int x) {
        ListNode little = new ListNode(0);
        ListNode littleTail = little;

        ListNode big = new ListNode(0);
        ListNode bigTail = big;
        while (pHead!=null) {
            if (pHead.val <x) {
                littleTail.next=pHead;
                littleTail=pHead;
            } else {
                bigTail.next=pHead;
                bigTail= pHead;
            }
            pHead=pHead.next;
        }
        littleTail.next = big.next;
        bigTail.next=null;
        return little.next;
    }

    public static void main(String[] args) {
        Partition partition = new Partition();
        ListNode listNode3 = new ListNode(3);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode1= new ListNode(1);
        listNode2.next=listNode1;
        listNode1.next=listNode3;
        ListNode partition1 = partition.partition(listNode2, 3);
        while (partition1!= null) {
            System.out.println(partition1.val);
            partition1=partition1.next;
        }
    }
}
